import time
import math

import addrutil
import dbmgr
import getliveip

class TrieNode:
  def __init__(self):
    self.sons = [None, None]
    self.all_home = None # set: {homeAS}
    self.cur_home = None # dict: {monip: curHomeAS}

class Trie:
  def __init__(self):
    self.cidx = {'0': 0, '1': 1}
    self.cset = "01"
    self.root_v4 = TrieNode()
    self.root_v6 = TrieNode()
    self.db = dbmgr.DBMgr()
    self.DBMaxAlarmID = 0
    self.astuples = {} # < astuple : [lastseen_v4/,v6, firstseen_v4/,v6] >
    
  def clear(self):
    self.root_v4 = TrieNode()
    self.root_v6 = TrieNode()
    self.db.close()

  def addAStuple(self, as0, as1, as2, ctime, is_ipv6):
    is_ipv6 = int(is_ipv6)
    if as0:
      asp = ("%u %u %u" % (as0, as1, as2))
    else:
      asp = ("%u %u" % (as1, as2))
    is_bad = False
    if asp in self.astuples: # update
      seen = self.astuples[asp]
      if ctime - seen[is_ipv6] > 86400:
        if seen[2 + is_ipv6] == 0:
          is_bad = True # is a new tuple
          seen[2 + is_ipv6] = ctime
        seen[is_ipv6] = ctime
        self.db.dbQueue.put(("astuple_u", (
          seen[0], seen[1], seen[2], seen[3], as0, as1, as2))) 
    else: # insert
      is_bad = True
      if is_ipv6 == 0:
        self.astuples[asp] = [ctime, 0, ctime, 0]
        self.db.dbQueue.put(("astuple_i", (ctime, 0, ctime, 0, as0, as1, as2)))
      else:
        self.astuples[asp] = [0, ctime, 0, ctime]
        self.db.dbQueue.put(("astuple_i", (0, ctime, 0, ctime, as0, as1, as2)))
    if is_bad:
      if as0:
        return (("^([0-9]+ )*%d (%d )+%d( [0-9]+)*$" % (as0, as1, as2)),
            ("%d %d %d" % (as0, as1, as2))) # bad_path_re, bad_path
      else:
        return (("^([0-9]+ )*%d %d( [0-9]+)*$" % (as1, as2)),
            ("%d %d" % (as1, as2))) # bad_path_re, bad_path
    return ("", "")

  #def zip_prefix_bin(self, prefix_bin):
  #  dec = 0
  #  for i in xrange(8):
  #    dec <<= 1
  #    if prefix_bin[i] == '1': dec += 1
  #  return "%d%s" % (dec, prefix_bin[8:])

  def getBlankSpace(self, cur, ipbeg, ipend, level):
    if not cur:
      return (ipbeg, ipend)
    if level > 0 and cur.all_home:
      return (None, None)
    if (not cur.sons[0]) and (not cur.sons[1]):
      return (ipbeg, ipend)
    if (ipbeg ^ ipend) <= 3:
      return (None, None)
    ipmid = (ipbeg | ((ipbeg ^ ipend) >> 1))
    beg, end = self.getBlankSpace(cur.sons[0], ipbeg, ipmid, 1)
    if beg:
      return (beg, end)
    beg, end = self.getBlankSpace(cur.sons[1], ipmid + 1, ipend, 1)
    if beg:
      return (beg, end)
    return (None, None)

  def walk_down_trie(self, is_ipv6, pfx_length, ipbeg_bin):
    if not is_ipv6:
      cur = self.root_v4
    else:
      cur = self.root_v6
    if (not ipbeg_bin) or (pfx_length <= 0):
      yield cur
    for ip in xrange(len(ipbeg_bin)):
      if pfx_length <= 0:
        break
      for jp in xrange(7, -1, -1):
        if pfx_length <= 0:
          break
        pfx_length -= 1
        if ord(ipbeg_bin[ip]) & (1 << jp):
          c = '1'
        else:
          c = '0'
        # for each c
        if cur.sons[self.cidx[c]] is None:
          cur.sons[self.cidx[c]] = TrieNode()
        cur = cur.sons[self.cidx[c]]
        yield cur
  
  def add(self, pfx, check_path, bad_path_re='', bad_path=''):
    # 1. Anomaly path segment
    if check_path:
      for j in xrange(len(pfx.path)-1, 0, -1): # from home to monitor
        # AS neighbors
        if pfx.path[j - 1] != 0 and pfx.path[j] != 0: # unknown ASN if path[j] == 0
          bpr, bp = self.addAStuple(
              0, pfx.path[j - 1], pfx.path[j],
              pfx.bgptime, pfx.is_ipv6)
          if not pfx.bad_path_re:
            pfx.bad_path_re = bpr
            pfx.bad_path = bp
          # AS tuple
          if j + 1 < len(pfx.path) and pfx.path[j + 1] != 0:
            bpr, bp = self.addAStuple(
                pfx.path[j - 1], pfx.path[j], pfx.path[j + 1],
                pfx.bgptime, pfx.is_ipv6)
            if not pfx.bad_path_re:
              pfx.bad_path_re = bpr
              pfx.bad_path = bp
    elif pfx.homeas != 0: # subsequent prefixes in the same UPDATE
      pfx.bad_path_re = bad_path_re
      pfx.bad_path = bad_path
    # 2. Anomaly home ASN
    if pfx.path and pfx.path[-1] == 0: # home ASN is unknown
      return
    # 2.1. find prefix in trie
    isNewHome = 1
    if pfx.homeas == 0: # DO NOT consider withdraw
      isNewHome = 0
    hasfather = 0
    for cur in self.walk_down_trie(pfx.is_ipv6, pfx.length, pfx.ipbeg_bin):
      if cur.all_home is not None:
        hasfather += 1
        if (isNewHome == 1) and (pfx.homeas in cur.all_home):
          isNewHome = 0
    if (cur.all_home is not None) and (hasfather > 0):
      hasfather -= 1 # '#father' should not include self [fixed: 2012.04.22]
    # 2.2. update database, table 'origin'
    if cur.cur_home:
      mchome = cur.cur_home.get(pfx.monip_bin, None)
      if (not mchome) or (mchome != pfx.homeas):
        cur.cur_home[pfx.monip_bin] = pfx.homeas
        self.db.dbQueue.put(("origin", pfx))
    else:
      cur.cur_home = {}
      cur.cur_home[pfx.monip_bin] = pfx.homeas
      self.db.dbQueue.put(("origin", pfx))
    # 2.3. blank space and live IP, for probing
    if isNewHome == 1 or pfx.bad_path_re:
      # 2.3.1. blank space
      # TODO: if all subprefix is withdraw, should return prefix itself
      pfx.hole_ipbeg, pfx.hole_ipend = self.getBlankSpace(
          cur, pfx.hole_ipbeg, pfx.hole_ipend, 0)
      if not pfx.hole_ipbeg: # TODO
        return
      # 2.3.2. live IP
      # golang version
      hole_ipbeg_str = addrutil.ip_int2str(pfx.hole_ipbeg, pfx.is_ipv6)
      if pfx.is_ipv6:
        hole_pfx_length = 128 - int(math.log(pfx.hole_ipend - pfx.hole_ipbeg + 1, 2))
      else:
        hole_pfx_length = 32 - int(math.log(pfx.hole_ipend - pfx.hole_ipbeg + 1, 2))
      hole_pfx = hole_ipbeg_str + '/' + str(hole_pfx_length)
      pfx.liveip, pfx.is_live = getliveip.getLiveIPGo(hole_pfx)
      if pfx.liveip == '':
        pfx.liveip = addrutil.ip_int2str(pfx.hole_ipbeg + 1, pfx.is_ipv6)
      # (OR) python version
      #pfx.liveip, pfx.is_live = getliveip.getLiveIP(
      #    pfx.hole_ipbeg, pfx.hole_ipend, pfx.is_ipv6)
    # 2.4. raise alarms
    # 2.4.1. alarm type
    hasson = 0
    if cur.sons[0] or cur.sons[1]:
      hasson = 1
    if (not hasfather) and (not hasson):
      prefixType = 1 # NewPrefix
    elif (not hasfather) and hasson:
      prefixType = 2 # ShortPrefix (2011-09-05 begin)
    elif hasfather and hasson:
      prefixType = 3 # MediaPrefix
    else:
      prefixType = 4 # LongPrefix
    # 2.4.2. put alarm into db queue
    if cur.all_home is None:
      if not hasfather: # do not consider new `shortest prefix`
        return
      if pfx.is_ipv6:   # TODO: currently do not consider IPv6
        return
      cur.all_home = set()
      if isNewHome == 1:
        # Alarm(1-4): new prefix. (Def. of 'AlarmType' in 'dbmgr.py')
        cur.all_home.add(pfx.homeas)
        self.DBMaxAlarmID += 1
        pfx.alarm_id = self.DBMaxAlarmID
        pfx.alarm_type = prefixType
        pfx.bad_path_re = "^([0-9]+ )*%d$" % pfx.homeas
        pfx.bad_path = str(pfx.homeas)
        self.db.dbQueue.put(("alarm", pfx))
        return
      elif pfx.bad_path_re:
        # Alarm(10-13): new prefix, not new home, but bad path segment
        self.DBMaxAlarmID += 1
        pfx.alarm_id = self.DBMaxAlarmID
        pfx.alarm_type = prefixType + 9
        self.db.dbQueue.put(("alarm", pfx))
        return
    else:
      if isNewHome == 1:
        # Alarm(6-9): existing prefix
        cur.all_home.add(pfx.homeas)
        self.DBMaxAlarmID += 1
        pfx.alarm_id = self.DBMaxAlarmID
        pfx.alarm_type = prefixType + 5
        pfx.bad_path_re = "^([0-9]+ )*%d$" % pfx.homeas
        pfx.bad_path = str(pfx.homeas)
        self.db.dbQueue.put(("alarm", pfx))
        return
      elif pfx.bad_path_re:
        # TODO current do not consider IPV6
        if pfx.is_ipv6:
          return
        # Alarm(14-17): existing prefix, not new home, but bad path segment
        self.DBMaxAlarmID += 1
        pfx.alarm_id = self.DBMaxAlarmID
        pfx.alarm_type = prefixType + 13
        self.db.dbQueue.put(("alarm", pfx))
        return

  def addexist(self, ipbeg_bin, pfx_length, homeas, is_ipv6, monip, isup, pfx_lens):
    is_newhome = True
    for cur in self.walk_down_trie(is_ipv6, pfx_length, ipbeg_bin):
      if cur.all_home and (homeas in cur.all_home):
        is_newhome = False
    # all_Home
    if cur.all_home == None:
      cur.all_home = set()
      ## stat. of prefix
      #if not is_ipv6:
      #  if pfx_length in pfx_lens:
      #    pfx_lens[pfx_length] += 1
      #  else:
      #    pfx_lens[pfx_length] = 1
    if is_newhome:
      cur.all_home.add(homeas)
    # cur_home
    if cur.cur_home == None:
      cur.cur_home = {}
    if isup == 1:
      cur.cur_home[monip] = homeas
    return

  def addexistAStuple(self, as0, as1, as2, lseen4, lseen6, fseen4, fseen6):
    #tuple = (" %s %s %s" % (
    #  addrutil.asn2sbin(as0), addrutil.asn2sbin(as1), addrutil.asn2sbin(as2)))
    if as0:
      ast = ("%u %u %u" % (as0, as1, as2))
    else:
      ast = ("%u %u" % (as1, as2))
    self.astuples[ast] = [lseen4, lseen6, fseen4, fseen6]

  def load(self, clear_expired=True):
    curtime = int(time.time())
    print '1'
    if clear_expired:
      print '2'
      nOutdatedHome = self.db.clearOutdatedHomeAS(curtime)
      nOutdatedTuple = self.db.clearOutdatedASTuple(curtime)
    else:
      print '3'
      nOutdatedHome = 0
      nOutdatedTuple = 0
    print '4'
    self.DBMaxAlarmID = self.db.getMaxAlarmID()
    n_pfx = 0
    print '5'
    po_lens = {}
    pfx_lens = {}
    print '6'
    for r in self.db.loadAllHomeAS():
      self.addexist(r[0], r[1], r[2], r[3], r[4], r[5], pfx_lens)
      n_pfx += 1
      #if not r[3]:
      #  if r[1] in po_lens:
      #    po_lens[r[1]] += 1
      #  else:
      #    po_lens[r[1]] = 1
    print '7'
    print self.db.loadAllAStuple()
    for r in self.db.loadAllAStuple():
      self.addexistAStuple(r[0], r[1], r[2], r[3], r[4], r[5], r[6])
    print 'debug:'
    print time.time()-curtime
    print nOutdatedHome
    print nOutdatedTuple
    print n_pfx
    print self.DBMaxAlarmID
    addrutil.log(int(time.time()), 0,
      '''INFO: Cost %ds. #ExpO %d, #ExpP %d, #Prefix %d, MaxAlarmID %d.''' % (
      time.time() - curtime, nOutdatedHome, nOutdatedTuple,
      n_pfx, self.DBMaxAlarmID))
    #addrutil.log(int(time.time()), 0,
    #  '''INFO: Cost %ds. #ExpO %d, #ExpP %d, #Prefix %d, MaxAlarmID %d.
    #  Prefix-Origin Lengths: %r
    #  Prefix Length: %r''' % (
    #  time.time() - curtime, nOutdatedHome, nOutdatedTuple,
    #  n_pfx, self.DBMaxAlarmID, po_lens, pfx_lens))

if __name__ == '__main__':
  pfxorigin = Trie()
  pfxorigin.add(addrutil.dotdec2bin("192.168.1/24"), 1, 0, 1, 1)
  pfxorigin.add(addrutil.dotdec2bin("192.168.1/24"), 1, 0, 2, 3)
  pfxorigin.add(addrutil.dotdec2bin("192.168.1/24"), 1, 0, 1, 7)
  pfxorigin.add(addrutil.dotdec2bin("192.168.1/24"), 1, 0, 3, 15)
  pfxorigin.add(addrutil.dotdec2bin("192.168/16"), 1, 0, 11, 11)
  pfxorigin.add(addrutil.dotdec2bin("192.168/16"), 1, 0, 12, 13)
  pfxorigin.add(addrutil.dotdec2bin("192.168/16"), 1, 0, 11, 17)
  pfxorigin.add(addrutil.dotdec2bin("192.168/16"), 1, 0, 13, 115)
  #pfxorigin.write("./log.mon", True, 1000)
  #pfxorigin.clear()
  #pfxorigin.load("./log.mon")
  print pfxorigin.find(addrutil.dotdec2bin("192.168.1/24"))
  print pfxorigin.find(addrutil.dotdec2bin("192.168.1.128/25"))
  print pfxorigin.find(addrutil.dotdec2bin("192.168/16"))
  print pfxorigin.find(addrutil.dotdec2bin("192.168.2/24"))
  print pfxorigin.find(addrutil.dotdec2bin("192.169/16"))
  #pfxorigin.write("./log.mon2", False, 0)

